% Version control information:
%\svnid{$Id: complejidad_algoritmica.tex 7 2009-04-20 22:10:35Z asalber $
%
\section{Complejidad Algorítmica}

%---------------------------------------------------------------------slide----
\begin{frame}
  \frametitle{Complejidad Algorítmica}
  \tableofcontents[sectionstyle=show/hide,hideothersubsections]
\end{frame}

\subsection{Algoritmos}

%---------------------------------------------------------------------slide----
\begin{frame}[fragile]
\frametitle{¿Qué es un algoritmo?}
\begin{definicion}[Algoritmo]
Un \textbf{algoritmo} es una secuencia de pasos orientados a la consecución de un objetivo.
\end{definicion}
\textbf{Ejemplo}. Receta de cocina para freir un huevo
\begin{lstlisting}
poner aceite en una sart\'en,
encender el fuego,
calentar el aceite,
coger un huevo,
romper la cascara,
verter el contenido del huevo en la sart\'en,
aderezar con sal,
depositar en un plato el huevo una vez frito.
\end{lstlisting}
... y ya está. ¿Seguro? ¿Cuánta sal hay que poner?
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{¿Qué es un algoritmo?}
Los pasos de un algoritmo deben tener una \textit{absoluta precisión}.

Corregimos:
\begin{lstlisting}
asomarse a la ventana y esperar a que pase un coche rojo,
poner 10 cc. de aceite de oliva en una sartén mediana,
encender la lavadora,
encender el fuego a medio gas,
calentar el aceite durante cinco minutos,
coger un huevo de gallina,
romper la cascara,
verter el contenido del huevo en la sart\'en,
aderezar con una pizca de sal,
depositar el huevo en un plato cuando la clara presente un aspecto consistente,
volver al paso 1.
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{¿Qué es un algoritmo?}
No basta con que los pasos sean precisos. Además:
\begin{itemize}
\item Cada paso dado debe conducir efectivamente a la consecución del objetivo.
\item Cada paso ha de poderse realizar en un tiempo finito.
\item La secuencia de instrucciones debe requerir tiempo finito.
\end{itemize}
\textbf{Ejemplo}. Cálculo del perímetro de una circunferencia a partir de su radio:
\begin{lstlisting}[mathescape=true]
Solicitar el radio de la circunferencia,
multiplicar el valor del radio por 2,
y multiplicar el resultado de la anterior operación por $\pi$;
el resultado de esta ultima operacion es el valor del perimetro.
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Características de un algoritmo}
\begin{itemize}
\item Ha de tener cero o más datos de entrada.
\item Ha de proporcionar uno o más datos de salida como resultados.
\item Cada paso del algoritmo ha de estar definido con exactitud, sin la menor ambigüedad.
\item Ha de ser finito, es decir, debe finalizar tras la ejecución de un número finito de pasos.
\item Ha de ser efectivo, es decir, cada uno de sus pasos ha de poder ejecutarse en tiempo finito con unos recursos determinados (en nuestro caso, con los que proporciona un ordenador).
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Del algoritmo al programa}
\begin{itemize}
\item Para que el ordenador realice los pasos de un algoritmo demos escribir el algoritmo en una notación que éste sea capaz de interpretar. Esa notación es un \alert{lenguaje de programación}.

\item Un algoritmo expresado en un lenguaje de programación es un \alert{programa}.

\item Cuando traducimos un algoritmo a un programa equivalente decimos que estamos \emph{implementando} el algoritmo en un lenguaje de programación determinado, y el programa es una \alert{implementación del algoritmo}.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Criterios de análisis de algoritmos}
\begin{itemize}
\item Un mismo problema puede ser resuelto de manera diferente por distintos algoritmos.
\begin{center}
\alert{¿Cómo saber qué algoritmo es mejor?}
\end{center}
\item Existen diferentes criterios para valorar la bondad de un algoritmo:
\begin{itemize}
\item Elegancia
\item Legibilidad
\item Interfaz de usuario y facilidad de manejo
\item Velocidad de ejecución
\item Memoria que consume
\end{itemize}

\item Nosotros estudiaremos aquí criterios basados en la eficiencia, es decir, en el mejor aprovechamiento de los recursos computacionales: \alert{espacio} (memoria) y \alert{tiempo} (velocidad de ejecución).
\end{itemize}
\end{frame}

\subsection{Análisis de la complejidad temporal}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste computacional}
\begin{itemize}
\item Estudiaremos dos costes de un algoritmo:
\begin{description}
\item [Coste Espacial:] la cantidad de memoria que consume.
\item [Coste Temporal:] el tiempo que necesita para resolver un problema.
\end{description}
Ambos determinan el \alert{Coste o Complejidad Computacional de un algoritmo}.

\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Antagonismo de los costes espacial y temporal}
\begin{itemize}
\item A menudo, los costes espacial y temporal suelen entrar en competencia.

\textbf{Ejemplo}. Mantener una colección de registros de todos los estudiantes de esta universidad.
\begin{itemize}
\item Con un vector con un elemento para cada registro de estudiante: tenemos acceso inmediato a cualquier elemento (muy poco tiempo) pero incurrimos en un gasto fuerte de memoria.
\item Con un vector a modo de cache de 20 elementos (muy poco espacio) pero teniendo que implementar un algoritmo de búsqueda para obtener el resto.
\end{itemize}

\item Existen dos principios básicos para elegir una solución que balancee de modo óptimo ambos conceptos:
\begin{itemize}
\item Elige unas estructuras de datos apropiadas para representar el modelo de datos del problema.
\item Usa algoritmos eficientes sobre las estructuras de datos elegidas.
\end{itemize}
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Microoptimización}
\begin{itemize}
\item Al escribir un algoritmo podemos estar tentados de realizar optimizaciones en cada paso del mismo, con el fin de gastar unos bytes menos de memoria o de ahorrar unas cuantas instrucciones  (microoptimizaciones).

\item \textbf{Ejemplo}.
\begin{center}
\alert{\ttfamily a++;} \quad   frente a \quad    \alert{\ttfamily a=a+1;}
\end{center}

\item Aunque la optimización es buena, abusar de ella puede ser contraproducente. Esto es muy peligroso y un error bastante común en programación.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Peligros de la microoptimización}
\begin{itemize}
\item Generan código más oscuro y difícil de entender (el código siempre hay que mantenerlo).
\item Hay que confiar en el compilador o intérprete que se use. Él es capaz de realizar microoptimizaciones mucho mejor que cualquier programador.
\item Es mucho más cara la hora de programador que la hora de CPU.
\item Todas las conjeturas que hagas sobre dónde gasta un programa su tiempo van a ser erróneas (ley del 90/10).
\end{itemize}

\vskip 1cm
\begin{center}
\emph{\alert{``Premature optimization is the root of all evil"}} \begin{scriptsize}Donald E. Knuth\end{scriptsize}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{¿Cómo analizar el coste de un algoritmo}
\begin{itemize}
\item ¿Contando el número de bytes de memoria que utiliza el programa?
\item ¿Midiendo con un cronómetro el tiempo que tarda en ejecutarse?
\begin{center}\alert{¡NO!}\end{center}
\item Inconvenientes:
\begin{itemize}
\item Debemos implementar el algoritmo:
\begin{itemize}
\item Dependencia del lenguaje
\item Dependencia de la experiencia del programador
\item Dependencia de la máquina en que se ejecute.
\end{itemize}
\item Resulta difícil medir fiablemente tiempos en ordenadores multiusuario.
\end{itemize}
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Principios del análisis de algoritmos}
\begin{itemize}
\item Independencia del ordenador sobre el que se ejecuten los programas,
\item Independencia del lenguaje de programación en que los implementemos, e
\item Independencia de los detalles de implementación (como el tipo de enteros escogido o las instrucciones concretas utilizadas).
\end{itemize}
\vskip 1cm
\begin{center}\alert{¡Queremos analizar algoritmos, no programas!}\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Cálculo mediante productos}
Comenzaremos estudiando la complejidad temporal, y para ello, compararemos tres programas para calcular $10^2$.
\vskip .5 cm
El primer programa usa directamente el producto para resolver el problema:
\begin{lstlisting}
// producto.java
public int producto() {
  int m = 10*10;
  return m;
}
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Cálculo mediante sumas}
El segundo suma 10 veces 10:
\begin{lstlisting}
// suma.java
public int suma() {
  int m = 0;
  for (int i=0; i<10; i++)
    m += 10;
  return m;
}
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Cálculo mediante incrementos}
El tercero repite 10 veces 10 incrementos unitarios:
\begin{lstlisting}
// incremento.java
public int incremento() {
  int m = 0;
    for (int i=0; i<10; i++)
      for (int j=0; j<10 ; j++)
        m++;
  return m;
}
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Comparación de programas}
El número de instrucciones que utiliza cada programa es
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Programa & Productos & Sumas & Incrementos & Asignaciones & Comparaciones \\
\hline Producto & 1 &  &  & 1 &  \\
\hline Suma &  & 10 & 10 & 12 & 11 \\
\hline Incremento &  &  & 210 & 12 & 121 \\
\hline
\end{tabular}
\end{center}
¿Cuál es más rápido?

¡Depende de la duración de las instrucciones elementales: sumas, productos, incrementos, asignaciones, comparaciones, salidas, etc!
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Máquina A}
Supongamos que en una máquina A, las instrucciones tardan lo siguiente:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Operación & Producto & Suma & Incremento & Asignación & Comparación \\
\hline Tiempo & 342 $\mu$s & 31 $\mu$s & 1 $\mu$s & 1 $\mu$s & 1 $\mu$s \\
\hline
\end{tabular}
\end{center}
\begin{columns}
\begin{column}{0.48\textwidth}
Entonces la duración es:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|}
\hline Programa & Duración \\
\hline Producto & 343 $\mu$s \\
\hline Suma & 343 $\mu$s \\
\hline Incremento & 343 $\mu$s \\
\hline
\end{tabular}
\end{center}
\begin{center}
\alert{¡Los tres tardan igual!}
\end{center}
\end{column}
\begin{column}{0.48\textwidth}
\begin{center}
\includegraphics[scale=0.25]{img/psi1}
\end{center}
\end{column}
\end{columns}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Máquina B}
Supongamos que en una máquina B, las instrucciones tardan lo siguiente:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Operación & Producto & Suma & Incremento & Asignación & Comparación \\
\hline Tiempo & 100 $\mu$s & 15 $\mu$s & 1 $\mu$s & 1 $\mu$s & 1 $\mu$s \\
\hline
\end{tabular}
\end{center}
\begin{columns}
\begin{column}{0.48\textwidth}
Entonces la duración es:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|}
\hline Programa & Duración \\
\hline Producto & 101 $\mu$s \\
\hline Suma & 183 $\mu$s \\
\hline Incremento & 343 $\mu$s \\
\hline
\end{tabular}
\end{center}
\begin{center}
\alert{¡Ahora el mejor es el producto!}
\end{center}
\end{column}
\begin{column}{0.48\textwidth}
\begin{center}
\includegraphics[scale=0.25]{img/psi2}
\end{center}
\end{column}
\end{columns}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de $10^2$}
\framesubtitle{Máquina C}
Supongamos que en una máquina C, las instrucciones tardan lo siguiente:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Operación & Producto & Suma & Incremento & Asignación & Comparación \\
\hline Tiempo & 100 $\mu$s & 5 $\mu$s & 1 $\mu$s & 1 $\mu$s & 1 $\mu$s \\
\hline
\end{tabular}
\end{center}
\begin{columns}
\begin{column}{0.48\textwidth}
Entonces la duración es:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|}
\hline Programa & Duración \\
\hline Producto & 101 $\mu$s \\
\hline Suma & 83 $\mu$s \\
\hline Incremento & 343 $\mu$s \\
\hline
\end{tabular}
\end{center}
\begin{center}
\alert{¡Ahora el mejor es el suma!}
\end{center}
\end{column}
\begin{column}{0.48\textwidth}
\begin{center}
\includegraphics[scale=0.25]{img/psi3}
\end{center}
\end{column}
\end{columns}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Cálculo del coste temporal}
\begin{itemize}
\item Como vemos, \alert{¡el coste de cada programa depende el ordenador que lo ejecute!}

\item ¿Qué ocurre si en lugar de calcular $10^2$ queremos calcular el cuadrado de cualquier número?

\item Generalicemos los programas anteriores para que calculen el cuadrado de cualquier entero $n$.

\item Anotaremos al margen el número de operaciones que conlleva cada instrucción.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Cálculo mediante productos}
El primer programa usa directamente el producto:
\begin{lstlisting}[mathescape]
// producto.java
public int producto(int n) {
  int m = n*n;    #\alert{$\leftarrow$ $1$ prod y $1$ asig}#
  return m;
}
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Cálculo mediante sumas}
El segundo suma $n$ veces $n$:
\begin{lstlisting}[mathescape]
// suma.java
public int suma(int n) {
  int m = 0;              #\alert{$\leftarrow$ $1$ asig}#
  for (int i=0; i<n; i++) #\alert{$\leftarrow$ $1$ asig, $n+1$ comp, $n$ incr}#
    m += n;               #\alert{$\leftarrow$ $1$ suma y 1 asig ($n$ veces)}#
  return m;
}
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Cálculo mediante incrementos}
El tercero repite $n$ veces $n$ incrmentos unitarios:
\begin{lstlisting}[mathescape]
// incremento.java
public int incremento(int n) {
  int m = 0;                   #\alert{$\leftarrow$ $1$ asig}#
    for (int i=0; i<n; i++)    #\alert{$\leftarrow$ $1$ asig, $n+1$ comp, $n$ incr}#
      for (int j=0; j<n; j++)  #\alert{$\leftarrow$ $1$ asig, $n+1$ comp, $n$ incr ($n$ veces)}#
        m++;                   #\alert{$\leftarrow$ $1$ incr ($n^2$ veces)}#
  return m;
}
\end{lstlisting}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Comparación de programas}
\begin{itemize}
\item El número de instrucciones que utiliza cada programa es
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Programa & Productos & Sumas & Incrementos & Asignaciones & Comparaciones \\
\hline Producto & 1 &  &  & 1 &  \\
\hline Suma &  & $n$ & $n$ & $n+2$ & $n+1$ \\
\hline Incremento &  &  & $2n^2+n$ & $n+2$ & $n^2+2n+1$ \\
\hline
\end{tabular}
\end{center}
\item Ahora el coste depende de $n$: cuanto mayor sea $n$ mayor será el coste.
\item Diremos que $n$ es el \alert{tamaño del problema}.
\item Calcularemos el coste de los algoritmos en función del tamaño del problema.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Máquina A}
Para la máquina A se tiene:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Operación & Producto & Suma & Incremento & Asignación & Comparación \\
\hline Tiempo & 342 $\mu$s & 31 $\mu$s & 1 $\mu$s & 1 $\mu$s & 1 $\mu$s \\
\hline
\end{tabular}
\vskip .5cm
\includegraphics[scale=0.6]{pic/figs/psil1}
\end{center}

\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Máquina B}
Para la máquina B se tiene:
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Operación & Producto & Suma & Incremento & Asignación & Comparación \\
\hline Tiempo & 100 $\mu$s & 15 $\mu$s & 1 $\mu$s & 1 $\mu$s & 1 $\mu$s \\
\hline
\end{tabular}
\vskip .5cm
\includegraphics[scale=0.6]{pic/figs/psil2}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Máquina B}
Hay varios tramos en los que resultan ganadores distintos programas:

\begin{columns}
\begin{column}{0.48\textwidth}
\begin{center}
\includegraphics[scale=0.5]{pic/figs/psil3}
\end{center}
\end{column}
\begin{column}{0.48\textwidth}
\begin{enumerate}[a)]
\item suma mejor que incremento,\\
incremento mejor que producto.
\item suma mejor que producto,\\
producto mejor que incremento.
\item producto mejor que suma,\\
suma mejor que incremento.
\end{enumerate}
\end{column}
\end{columns}
\vskip 0.5cm
A partir de $n=13$ siempre gana producto.
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Un caso extremo}
Supongamos una máquina donde el producto es muy costoso.
\begin{center}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline Operación & Producto & Suma & Incremento & Asignación & Comparación \\
\hline Tiempo & 600 $\mu$s & 15 $\mu$s & 1 $\mu$s & 1 $\mu$s & 1 $\mu$s \\
\hline
\end{tabular}
\vskip .5cm
\includegraphics[scale=0.6]{pic/figs/psil4}
\end{center}
\vskip 0.5cm
De nuevo, a partir de un cierto tamaño el producto vuelve a ganar.
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Evolución del coste temporal con el tamaño del problema}
\begin{itemize}
\item Independientemente del coste de cada operación básica, producto siempre acaba siendo mejor que los otros dos programas.
\begin{center}
¿Por qué?
\end{center}
\item Un método que tarda un tiempo constante siempre acaba siendo mejor que uno cuyo tiempo depende linealmente del tamaño del problema.
\item Y un método cuyo tiempo depende linealmente del tamaño del problema, siempre llega un punto para el que es mejor que otro método cuyo tiempo de ejecución crece cuadráticamente con el tamaño del problema.
\item El algoritmo producto es \emph{asintóticamente} más eficiente que los otros, y que el algoritmo suma es \emph{asintóticamente} más eficiente que el incremento.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste temporal asintótico}
\begin{itemize}
\item Si queremos ver cómo evoluciona el coste con el tamaño, podemos hacer estudios asintóticos independientes del coste de cada operación.
\item El \alert{coste asintótico} expresa el coste de un algoritmo en función del tamaño del problema para tamaños grandes ($n\rightarrow \infty$).
\begin{center}
¿Nos basta con eso?
\end{center}
\item Sí, por varias razones:
\begin{itemize}
\item Los programas son especialmente útiles para resolver problemas de gran tamaño.
\item Simplifica el análisis al hacerlo independiente del coste de las operaciones elementales. Esto facilita la comparación de algoritmos.
\item Y hay muchas más...
\end{itemize}
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Determinación del tamaño del problema}
\begin{itemize}
\item Puesto que el coste depende del tamaño del problema, antes de empezar el análisis de un algoritmo hemos de tener claro qué parámetro determina el tamaño del problema.
\item ¿Cuál es el tamaño del problema en el siguiente programa?
\begin{lstlisting}
// pertenece.java
public boolean pertenece(String s, char c){
  for (int i = 0; i < s.length(); i++)
    if (s.charAt(i)==c) return true;
  return false;
}
\end{lstlisting}
\item En este caso el tamaño no viene dado de forma explícita, sino que es la longitud de la cadena de entrada ({\ttfamily s.length()}).
\end{itemize}
\end{frame}


\subsection{Coste temporal en pasos}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Paso de cómputo}
\begin{definicion}[Paso de cómputo]
Se llama \textbf{paso de cómputo} (step) a un segmento de código cuyo tiempo de proceso no depende del tamaño del problema considerado y está acotado por alguna constante.
\end{definicion}

Son siempre pasos:
\begin{itemize}
\item Las operaciones aritméticas,
\item Las operaciones lógicas,
\item Las comparaciones entre escalares,
\item Los accesos a variables escalares,
\item Los accesos a elementos de vectores o matrices,
\item La lectura de un valor escalar,
\item La escritura de un valor escalar, \ldots
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste computacional temporal}
\begin{definicion}[Coste computacional temporal]
Se llama \textbf{coste computacional temporal} de un programa al número de pasos del programa expresado en función del tamaño del problema.
\end{definicion}
\begin{itemize}
\item El coste computacional temporal es una función que depende del tamaño del problema $f(n)$.
\item Utilizaremos esta función para comparar la eficiencia temporal de los algoritmos.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Cálculo mediante productos}
\begin{lstlisting}[mathescape]
// producto.java
public int producto(int n) {
  int m = n*n;    #\alert{$\leftarrow$ $2$ pasos}#
  return m;
}
\end{lstlisting}
El coste computacional temporal es $2$ (constante).
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Cálculo mediante sumas}
\begin{lstlisting}[mathescape]
// suma.java
public int suma(int n) {
  int m = 0;              #\alert{$\leftarrow$ $1$ paso}#
  for (int i=0; i<n; i++) #\alert{$\leftarrow$ $2n+2$ pasos}#
    m += n;               #\alert{$\leftarrow$ $2$ pasos ($n$ veces)}#
  return m;
}
\end{lstlisting}
El coste computacional temporal es $4n+3$ (lineal).
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo: Coste temporal del cálculo de un cuadrado}
\framesubtitle{Cálculo mediante incrementos}
\begin{lstlisting}[mathescape]
// incremento.java
public int incremento(int n) {
  int m = 0;                       #\alert{$\leftarrow$ $1$ paso}#
    for (int i = 0; i < n; i++)    #\alert{$\leftarrow$ $2n+2$ pasos}#
      for (int j = 0; j < n ; j++) #\alert{$\leftarrow$ $2n+2$ pasos ($n$ veces)}#
        m++;                       #\alert{$\leftarrow$ $1$ paso ($n^2$ veces)}#
  return m;
}
\end{lstlisting}
El coste computacional temporal es $3n^2+4n+3$ (cuadrático).
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Las constantes no importan}
\begin{itemize}
\item Resumiendo tenemos
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
 Programa       & producto &  suma  & incremento  \\
\hline
 Coste temporal &    $4$     & $4n+3$ & $3n^2+4n+3$ \\
\hline
\end{tabular}
\end{center}
\item El valor concreto de los factores de cada término en estas expresiones no importa desde el punto de vista asintótico.
\item Cualquier secuencia de pasos cuya longitud no depende del tamaño del problema cuenta como una cantidad constante de pasos.
\item Por tanto podemos escribir
\begin{center}
\begin{tabular}{|l|c|c|c|}
\hline
 Programa       & producto &  suma  & incremento  \\
\hline
 Coste temporal &    $c_0$     & $c_2n+c_1$ & $c_5n^2+c_4n+c_3$ \\
\hline
\end{tabular}
\end{center}
siendo $c_i$ constantes.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El lenguaje de programación no importa}
Si por ejemplo implementamos el algoritmo suma en C++ tenemos
\begin{lstlisting}[mathescape, language=c]
// suma1.cpp
using namespace std;
int suma(int n){
  int m=0;                   #\alert{$\leftarrow$ $1$ paso}#
  for (int i=0; i<n; i++){   #\alert{$\leftarrow$ $2n+2$ pasos}#
    m += n;                  #\alert{$\leftarrow$ $2$ pasos ($n$ veces)}#
  }
  return m;
}
\end{lstlisting}
El coste computacional temporal es $4n+3$ (¡sigue siendo lineal!).
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Los detalles de implementación tampoco importan}
Si implementamos el algoritmo anterior con un bucle \texttt{while} en vez de un \texttt{for}, tenemos:
\begin{lstlisting}[mathescape, language=c]
// suma2.cpp
using namespace std;
int suma(int n){
  int i=0,m=0;      #\alert{$\leftarrow$ $2$ pasos}#
  while(i<n){       #\alert{$\leftarrow$ $n+1$ pasos}#
      m += n;       #\alert{$\leftarrow$ $2$ pasos ($n$ veces)}#
      i++;          #\alert{$\leftarrow$ $1$ paso ($n$ veces)}#
  }
  return m;
}
\end{lstlisting}
El coste computacional temporal es $4n+3$ (¡sigue siendo lineal!).
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Instancia de un problema}
\begin{definicion}[Instancia de un problema]
Llamaremos \textbf{instancia de un problema} a una entrada concreta de tamaño $n$.
\end{definicion}
\begin{itemize}
\item \textbf{Ejemplo}. Consideremos la función que determina la pertenencia de un carácter a una cadena:
\begin{lstlisting}
// pertenece.java
public boolean pertenece(String s, char c){
  for (int i = 0; i < s.length(); i++)
    if (s.charAt(i)==c) return true;
  return false;
}
\end{lstlisting}
\item Ya vimos que el tamaño del problema era la longitud de la cadena.
\item Así, \verb#c="casa"# y \verb#a='c'# sería una instancia de tamaño 4, mientras que \verb#c="coche"# y \verb#a='z'# sería una instancia de tamaño 5.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El número de pasos depende de la instancia}
\begin{itemize}
\item En muchos algoritmos, el tiempo de ejecución variará no sólo para las entradas de distintos tamaños, sino también para las distintas entradas del mismo tamaño.
\item \textbf{Ejemplo}. Si consideramos el programa anterior, y tomamos las instancias
\begin{itemize}
\item Instancia 1: \verb#c="casa"# y \verb#a='c'#,
\item Instancia 2: \verb#c="casa"# y \verb#a='z'#.
\end{itemize}
Las dos son del mismo tamaño, pero \emph{¿tardará el mismo tiempo el ejecutarse la función para ambas?}
\item \textbf{¡No!} Para la instancia 1 la función ejecutaría 4 pasos, mientras que para la instancia 2 ejecutaría 15 pasos.
Así pues, \alert{\emph{¡el coste temporal de un algoritmo no depende sólo de el tamaño del problema, sino también de las instancias!}}.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste para cada instancia}

Cuando ejecutemos un algoritmo con distintas instancias, obtendremos diferentes costes temporales, incluso para un mismo tamaño $n$:
\vskip .5cm
\begin{center}
\includegraphics[scale=0.6]{pic/figs/dots1}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Mejor y pero casos}
\begin{itemize}
\item Podríamos medir el coste para las distintas instancias de cada tamaño, pero eso resulta muy costoso y en muchos casos imposible.
\item Por ello nos centraremos en las dos situaciones extremas del algoritmo:
\alert{el mejor de los casos}, y
\alert{el peor de los casos}.
\item Ambos casos dependen del algoritmo; en nuestro ejemplo:
\begin{itemize}
\item Mejor caso: si el carácter es el primero de la cadena.
\item Peor caso: si el carácter no está en la cadena.
\end{itemize}
\item \alert{¡Ojo!} Ambos casos se calculan siempre para un valor fijo de $n$ dado.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Análisis del mejor y peor caso}
\framesubtitle{Un ejemplo}
Consideremos de nuevo el algoritmo de pertenencia de un carácter a una cadena.
\begin{itemize}
\item Análisis del mejor caso de tamaño $n$ (el carácter está en la primera posición de la cadena):
\begin{lstlisting}
// pertenece.java
public boolean pertenece(String s, char c){
  for (int i = 0; i < s.length(); i++)      #\alert{$\leftarrow$ $2$ pasos}#
    if (s.charAt(i)==c) return true;        #\alert{$\leftarrow$ $1$ pasos}#
  return false;
}
\end{lstlisting}
El mejor caso tiene un coste 3 (constante $c_0$).
\item Análisis del peor caso de tamaño $n$ (el carácter no está en la cadena):
\begin{lstlisting}
// pertenece.java
public boolean pertenece(String s, char c){
  for (int i = 0; i < s.length(); i++)      #\alert{$\leftarrow$ $2n+2$ pasos}#
    if (s.charAt(i)==c) return true;        #\alert{$\leftarrow$ $n$ pasos}#
  return false;
}
\end{lstlisting}
El peor caso tiene un coste $3n+2$ (lineal $c_1+c_2n$).
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Acotación de casos}
El tiempo invertido en resolver cada instancia está acotado inferiormente por una función constante $c_0$ y acotado superiormente por una función de la lineal $c_2n+c_1$.
\vskip .5cm
\begin{center}
\includegraphics[scale=0.6]{pic/figs/dots2}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Caso promedio}
\begin{itemize}
\item Podríamos calcular el coste promedio si conociésemos la distribución de probabilidades de las instancias, aunque suele ser difícil de calcular.
\item Lo único que sabemos a ciencia cierta sobre la función de coste promedio es que siempre está comprendida entre la función de coste en el mejor caso y la función de coste en el peor caso.
\end{itemize}
\vskip .5cm
\begin{center}
\includegraphics[scale=0.6]{pic/figs/dots3}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{¿Qué coste es más interesante?}
\begin{itemize}
\item Tenemos tres conceptos distintos de coste asintótico:
\begin{itemize}
\item Coste en el mejor de los casos.
\item Coste en el peor de los casos.
\item Coste promedio.
\end{itemize}
\begin{center}
¿Cuál de ellos resulta más informativo?
\end{center}
Depende...
\item El coste en el caso promedio es muy interesante, \emph{pero suele ser difícil de calcular}.
\item En ciertas aplicaciones resulta más relevante el coste en el peor de los casos (ej.: máximo tiempo de reacción ante un problema en reactor nuclear).
\item En otras aplicaciones el más interesante es el coste en el mejor de los casos (ej.: ordenar datos de clientes cuando están casi ordenados).
\end{itemize}
\begin{center}
\emph{\alert{¡Nos centraremos en el coste en el mejor y en el peor de los casos!}}
\end{center}
\end{frame}


\subsection{Coste temporal asintótico}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Notación asintótica}
\begin{itemize}
\item Estudiaremos la evolución del coste temporal con el tamaño del problema (coste asintótico) tanto en el mejor como en el peor caso. con el
\item Para simplificar el análisis aprenderemos a caracterizar el coste temporal mediante funciones simples que acoten superior e inferiormente el coste de toda instancia para tamaños suficientemente grandes.
\item Para ello necesitamos definir familias de cotas.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Orden de una función de coste}
\begin{definicion}[Orden]
Dada una función de coste $f: \mathbb{N}\longrightarrow \mathbb{R}^+$, se define el \textbf{orden} de $f$ como la familia de funciones
\[
O(f)=\{g: N\longrightarrow \mathbb{R}^+\ |\ \exists c\in \mathbb{R}^+, \exists n_0\in \mathbb{N}\, :\, \forall n\geq n_0,\, g(n)\leq cf(n)\}
\]
\end{definicion}
$O(f)$ es la familia de funciones que asintóticamente están acotadas superiormente por un múltiplo de $f$.

\begin{center}
\includegraphics[scale=0.3]{img/cotasup}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de ordenes}
\begin{itemize}
\item ¿Pertenece $t(n)=n+1$ a $O(n)$?

Si, pues siempre hay un valor $n_0$ y un valor $c$ para los que $n+1\leq cn$ si $n\geq n_0$. Por ejemplo, si $n_0=1$ y $c=2$,
\[
t(n)=n+1 \leq 2n\ \forall n\geq1.
\]
La expresión se lee tanto ``$t(n)$ pertenece a $O(n)$'' como ``$t(n)$ es $O(n)$''.
\item ¿Pertenece $t(n)=10n^2+4n+2$ a $O(n^2)$?

Si, pues $t(n)=10n^2+4n+2\leq 11n^2$ $\forall n\geq 5$.

\item ¿Pertenece $t(n)=10n^2+4n+2$ a $O(n)$?

No, pues no existen valores  de $c$ y $n_0$ tales que $t(n)=10n^2+4n+2 \leq cn$ $\forall n\geq n_0$. Por muy grande que sea $c$, $t(n)$ siempre acaba siendo más grande que $cn$.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Omega de una función de coste}
\begin{definicion}[Omega]
Dada una función de coste $f: N\longrightarrow \mathbb{R}^+$, se define el \textbf{omega} de $f$ como la familia de funciones
\[
\Omega(f)=\{g: \mathbb{N}\longrightarrow \mathbb{R}^+\ |\ \exists c\in \mathbb{R}^+, \exists n_0\in \mathbb{N}\, :\, \forall n\geq n_0,\, g(n)\geq cf(n)\}
\]
\end{definicion}
$O(f)$ es la familia de funciones que asintóticamente están acotadas inferiormente por un múltiplo de $f$.

\begin{center}
\includegraphics[scale=0.3]{img/cotainf}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de omegas}
\begin{itemize}
\item ¿Es $\Omega(n^2)$ la función $t(n) = 10n^2 + 4n + 2$?

Sí, ya que para $n_0=0$ (es decir, $n\geq 0$) y $c=10$, se tiene:
$t(n)=10n^2+4n+2\geq 10n^2$ $\forall n\geq0$.

\item ¿Pertenece $t(n) = 4\cdot 2^n - 6n^2$ a $\Omega(2^n)$?

Si, pues $t(n) = 4\cdot 2^n - 6n^2 \geq 2^n$ $\forall n\geq4$.
\item ¿Pertenece $t(n)=n+1$ a $\Omega(n^2)$?

No, pues por muy pequeño que sea $c$, $cn^2$ siempre acaba siendo mayor que $n+1$.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Zeta de una función de coste}
\begin{definicion}[Zeta]
Dada una función de coste $f: N\longrightarrow \mathbb{R}^+$, se define el \textbf{zeta} (u orden exacto) de $f$ como la familia de funciones que pertenecen al mismo tiempo al orden y al omega de $f$.
\[
\Theta(f)=O(f)\cap \Omega(f).
\]
\end{definicion}
$\Theta(f)$ es la familia de funciones que asintóticamente están acotadas superior e inferiormente por un múltiplos de $f$.

\begin{center}
\includegraphics[scale=0.3]{img/cotadoble}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de Zetas}
\begin{itemize}
\item $t(n) = 3n + 2$ es $\Theta(n)$, ya que:
\begin{itemize}
\item Es $O(n)$: $t(n) \leq 4n$  $\forall n\geq 2$.
\item Es $\Omega(n)$: $t(n) \geq 2n$ $\forall n\geq 1$.
\end{itemize}

\item $t(n) = 10n^2 + 4n + 2$ es $\Theta(n^2)$ ya que, como vimos en ejemplos anteriores, es $\Omega(n^2)$0 y $O(n^2)$.

\item La función
\[
\left\{
  \begin{array}{ll}
    n^2, & \hbox{si $n$ es par;} \\
    n, & \hbox{si $n$ es impar.}
  \end{array}
\right.
\]
no pertenece a ningún zeta, ya que es $O(n^2)$ y $\Omega(n)$ pero no es $O(n)$ ni $\Omega(n^2)$.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Jerarquía de cotas}
Entre las familias de ordenes hay una jerarquía de cotas:
\[
\begin{array}{c}
O(1)\subset O(\log n) \subset O(\sqrt{n}) \subset O(n)\subset O(n\log n) \subset \ldots\\
\ldots \subset O(n^2) \subset O(n^3) \subset O(2^n) \subset O(3^n) \subset O(n!) \subset O(n^n)
\end{array}
\]
y también entre las familias de omegas:
\[
\begin{array}{c}
\Omega(1)\supset \Omega(\log n) \supset \Omega(\sqrt{n}) \supset \Omega(n)\supset \Omega(n\log n) \supset \ldots\\
\ldots \supset \Omega(n^2) \supset \Omega(n^3) \supset \Omega(2^n) \supset \Omega(3^n) \supset \Omega(n!) \supset \Omega(n^n)
\end{array}
\]
Así, por ejemplo, si $3n+2$ es $O(n)$, también es $O(n^2)$ y $O(2^n)$, pero \emph{siempre proporcionaremos como cota el orden que más se ajusta a la función}.
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Clasificación de las familias de cotas}
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 & Constantes & $O(1)$ \\
\cline{2-3}
Sublineales & Logarítmicas & $O(\log n)$ \\
\cline{2-3}
 & Raíces & $O(\sqrt{n})$ \\
\hline
Lineales & Lineales & $O(n)$ \\
\hline
 & Loglineales & $O(n\log n)$ \\
\cline{2-3}
& Polinómicas & $O(n^k)$ \\
\cline{2-3}
Superlineales &  & $O(k^n)$ \\
\cline{3-3}
 & Exponenciales & $O(n!)$ \\
\cline{3-3}
 &  & $O(n^n)$ \\
\hline
\end{tabular}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Clasificación de Algoritmos}
\begin{itemize}
\item Diremos que el coste temporal de un algoritmo es lineal cuando es $O(n)$ y cúbico cuando es $O(n^3)$. De hecho, abusando del lenguaje diremos que el algoritmo es lineal o cúbico, respectivamente.
\item Así pues, esta notación nos sirve para agrupar los algoritmos en familias.
\item ¿Qué implica, a efectos prácticos, que un coste sea logarítmico, lineal, exponencial, etc.?

Lo mejor será que comparemos algunas gráficas de crecimiento.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Funciones lineales y sublineales}
\begin{center}
\includegraphics[scale=0.5]{img/sublineales}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Comparación de algoritmos lineales y sublineales}
\begin{itemize}
  \item Un algoritmo de coste constante ejecuta un número constante de instrucciones o acotado por una constante independiente del tamaño del problema. A la larga es mejor que cualquier algoritmo de coste no constante.
\item El coste de un algoritmo logarítmico crece muy lentamente en relación al tamaño del problema. Por ejemplo, si en resolver un problema de tamaño $n = 10$ tarda 1 $\mu$s, puede tardar $2$ $\mu$s en resolver un problema $10$ veces más grande ($n = 10^2$).
\item Un algoritmo cuyo coste es $\Theta(\sqrt n)$ crece a un ritmo superior a
otro que es $\Theta(\log n)$, pero no llega a presentar un crecimiento lineal. Cuando el tamaño se multiplica por cuatro, el coste se multiplica por dos.
\begin{center}
\emph{\alert{¡El coste de estos algoritmos crece poco
cuando $n$ se hace muy grande!}}
\end{center}
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Funciones lineales y superlineales}
\begin{center}
\includegraphics[scale=0.5]{img/superlineales}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Comparación de algoritmos lineales y superlineales}
\begin{itemize}
\item Un algoritmo que es $\Theta(n\log n)$ presenta un crecimiento del coste ligeramente superior al de un algoritmo lineal. Por ejemplo, si tardamos $10$ $\mu$s en resolver un problema de tamaño $1000$, puede que tardemos $22$ $\mu$s, poco más del doble, en resolver un problema de tamaño $2000$.
\item Un algoritmo cuadrático $\Theta(n^2)$ empieza a ser poco útil para tamaños grandes, pues pasar a tratar con un problema el doble de grande requiere cuatro veces más tiempo.
\item Un algoritmo exponencial raramente es útil. Si resolver un problema de tamaño $10$ requiere una cantidad de tiempo $10$ $\mu$s, con un algoritmo $\Theta(2^n)$, tratar con uno de tamaño el doble $20$ requiere $100$ $\mu$s (\emph{¡el cuadrado del tiempo!}).
\item En los algoritmos exponenciales incluimos los de coste factorial ($n!$) aunque no sean técnicamente exponenciales.
\begin{center}
\emph{\alert{¡El coste de estos algoritmos crece mucho
cuando $n$ se hace muy grande!}}
\end{center}

\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Comparación del crecimiento}
Para comparar supondremos que todas las instancias de tamaño $n = 1$ de un problema se resuelven en $1$ $\mu$s.\footnote{Recuerda que  $1$ $\mu$s supone unas $400$ instrucciones de código máquina en una CPU de $1$ GHz.}
\begin{center}
\rowcolors{1}{blue!10!white}{blue!20!white}
\arrayrulewidth 0.8pt
\begin{tabular}{|l|c|c|c|c|c|}
\hline \rowcolor{white!90!black}
 Coste              &  $n=1$  &   $n=5$   &  $n=10$   &      $n=50$       &       $n=100$        \\
\hline \hline
 Constante          & $1\mu$s &  $1\mu$s  &  $1\mu$s  &      $1\mu$s      &       $1\mu$s        \\
\hline
 Logarítmico        & $1\mu$s & $1.7\mu$s &  $2\mu$s  &     $2.7\mu$s     &       $3\mu$s        \\
\hline
 Lineal             & $1\mu$s &  $5\mu$s  & $10\mu$s  &     $50\mu$s      &      $100\mu$s       \\
\hline
 Loglineal          & $1\mu$s & $4.5\mu$s & $11\mu$s  &     $86\mu$s      &      $201\mu$s       \\
\hline
 Cuadrático         & $1\mu$s & $25\mu$s  & $100\mu$s &      $2.5$ms      &        $10$ms        \\
\hline
 Cúbico             & $1\mu$s & $125\mu$s &   $1$ms   &      $125$ms      &         $1$s         \\
\hline
 Exponencial($2^n$) & $1\mu$s & $32\mu$s  &   $1$ms   & $1$ año y 2 meses & $40\cdot 10^6$ eones \\
\hline
\end{tabular}
\end{center}
Para hacernos una idea de la magnitud de las últimas cifras, \emph{un eón son mil millones de años}, y los científicos estiman actualmente que la edad del universo es de entre 13 y 14 eones.
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Comparación del crecimiento}
\framesubtitle{El ordenador más rápido del mundo}
El último número es bárbaro, salvajemente alto. Pero, ¿qué ocurriría si pudiésemos construir un ordenador ideal? Es decir, uno en el que los registros de la CPU pueden ser cargados con datos a la velocidad de la luz.
Con este ordenador obtendríamos los siguientes números:
\begin{center}
\rowcolors{1}{blue!10!white}{blue!20!white}
\arrayrulewidth 1pt
\begin{tabular}{|l|c|c|c|c|c|}
\hline \rowcolor{white!90!black}
 Coste              &   $n=1$    &    $n=5$    &   $n=10$   &   $n=50$    &   $n=100$   \\
\hline\hline
 Constante          & $0.01$ns & $0.01$ns  & $0.01$ns & $0.01$ns  & $0.01$ns  \\
\hline
 Logarítmico        & $0.01$ns & $0.017$ns & $0.02$ns & $0.027$ns & $0.03$ns  \\
\hline
 Lineal             & $0.01$ns & $0.05$ns  & $0.1$ns  &  $0.5$ns  &    $1$ns    \\
\hline
 Loglineal          &  $0.1$ns   &  $0.45$ns   & $0.11$ns & $0.86$ns  & $2.01$ns  \\
\hline
 Cuadrático         & $0.1$ns  & $0.25$ns  &  $1$ns   &   $25$ns    &   $100$ns   \\
\hline
 Cúbico             & $0.01$ns & $1.25$ns  &   $10$ns   &   $125$ns   &  $10\mu$s   \\
\hline
 Exponencial($2^n$) & $0.01$ns & $0.32$ns  &   $10$ns   & $6$ minutos & $400$ eones \\
\hline
\end{tabular}
\vskip .5cm
\emph{\alert{¡Un algoritmo exponencial es inviable por mucho que avance la tecnología!}}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Comparación del crecimiento}
\framesubtitle{Tamaños del problema grandes}
Además estamos hablando de un tamaño de sólo 100 elementos. ¿Qué pasaría con 10.000?

Veamos sólo algoritmos no exponenciales para valores más elevados de $n$:
\begin{center}
\rowcolors{1}{blue!10!white}{blue!20!white}
\arrayrulewidth 1pt
\begin{tabular}{|l|c|c|c|}
\hline \rowcolor{white!90!black}
 Coste              &   $n=1000$    &    $n=10000$    &   $n=100000$\\
\hline\hline
 Constante          & $1\mu$s & $1\mu$s  & $1\mu$s \\
\hline
 Logarítmico        & $4\mu$s & $5\mu$s & $6\mu$s \\
\hline
 Lineal             & $1$ms & $10$ms  & $100$ms \\
\hline
 Loglineal          &  $3$ms   &  $40$ms   & $500$ms \\
\hline
 Cuadrático         & $1$s  & $100$s  &  $16.5$m \\
\hline
 Cúbico             & $16.5$m & $1.5$días  &   $32$años  \\
\hline
\end{tabular}
\vskip .5cm
\emph{\alert{¡Incluso con algoritmos no exponenciales el coste puede ser excesivo!}}
\end{center}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Propiedades de las cotas}
\begin{itemize}
\item Producto de una función por una constante:
\begin{itemize}
\item Si $t(n)\in O(f)$ entonces $ct(n)\in O(f)$.
\item Si $t(n)\in \Omega(f)$ entonces $ct(n)\in\Omega(f)$.
\end{itemize}
\item Suma de funciones:
\begin{itemize}
\item Si $t_1(n)\in O(f_1)$, $t_2(n)\in O(f_2)$ entonces
            $t_1(n)+t_2(n)\in O(\max(f_1, f_2))$.
\item Si $t_1(n)\in\Omega(f_1)$, $t_2(n)\in\Omega(f_2)$ entonces
            $t_1(n)+t_2(n)\in\Omega(\max(f_1, f_2))$.
\end{itemize}
\item Producto de funciones:
\begin{itemize}
\item Si $t_1(n)\in O(f_1)$, $t_2(n)\in O(f_2)$ entonces $t_1(n)\cdot t_2(n)\in O(f_1\cdot f_2)$.
\item Si $t_1(n)\in \Omega(f_1)$, $t_2(n)\in \Omega(f_2)$ entonces $t_1(n)\cdot t_2(n)\in \Omega(f_1\cdot f_2)$.
\end{itemize}

\item Una consecuencia de estas propiedades es que cualquier polinomio de grado $k$ es $\Theta(n^k)$.

\item Si $t(n)\in O(f)$ y $f(n)\in O(g)$ entonces $t(n)\in O(g)$ (\emph{transitividad del orden}).
\item Si $O(f)\subseteq O(g)$ entonces $\Omega(g)\subseteq\Omega(f)$.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Simplificación de cotas}
\begin{itemize}
  \item En el cálculo de cotas, podemos resumir las anteriores propiedades de la notación orden (y omega y zeta, por supuesto) de forma simplificada como:
\begin{itemize}
\item Eliminar las constantes de proporcionalidad.
\item Guardar sólo el término dominante.
\item Usar las propiedades de suma y producto para simplificar.
\end{itemize}

\item Como se ve, la notación asintótica simplifica mucho la expresión de los costes, pues permite su reducción a su término dominante, eliminando todas las constantes de proporcionalidad y términos adicionales.
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Cálculo de cotas mediante límites}
\begin{teorema}[Límite]
Dadas dos funciones de coste $f,g: \mathbb{N}\longrightarrow \mathbb{R}^+$, tales que
\[
\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)} = l,\]
entonces
\begin{itemize}
\item Si $l=0$, entonces $f\in O(g)$, pero $g\not \in O(f)$, es decir, $O(f)\subset O(g)$.
\item Si $l=\infty$, entonces $g\in O(f)$, pero $f\not \in O(g)$, es decir, $O(g)\subset O(f)$.
\item Si $l\in \mathbb{R}^+$, entonces $f\in O(g)$ y $g \in O(f)$, es decir, $O(f)=O(g)$, y también $\Theta(f)=\Theta(g)$.
\end{itemize}
\end{teorema}

\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algunas cotas precalculadas}
\[
\rowcolors{1}{blue!10!white}{blue!20!white}
\arrayrulewidth 0.8pt
\begin{array}{|c|c|l|}
\hline \rowcolor{white!90!black}
             t(n)             &   \mbox{Orden}   & \mbox{Observaciones} \\
\hline\hline
              c               &    \Theta (1)    &     \forall c>0      \\
\hline
\displaystyle    \sum_{i=0}^{k} c_in^i     &   \Theta (n^k)   &   \forall c_i\in \mathbb{R}   \\
\hline
\displaystyle        \sum_{i=1}^{n} i^k      & \Theta(n^{k+1})  &   \forall k\in \mathbb{N}^+   \\
\hline
\displaystyle      \sum_{i=1}^{n} (n-i)^k    & \Theta(n^{k+1})  &   \forall k\in \mathbb{N}^+   \\
\hline
           \log(n!)           & \Theta (n\log n) &                      \\
\hline
\displaystyle        \sum_{i=1}^{n} k^i      &   \Theta(k^n)    &     \forall k>1      \\
\hline
\displaystyle    \sum_{i=1}^{n} \frac{1}{i}  &  \Theta(\log n)  &                      \\
\hline
\displaystyle   \sum_{i=1}^{n} \frac{i}{k^i} &    \Theta(1)     &     \forall k>1      \\
\hline
\end{array}
\]
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una instrucción simple}
Las instrucciones simples, tales como las asignaciones, las operaciones aritméticas y lógicas, el acceso a miembros de arrays , vectores o estructuras, e instrucciones tales como \verb"goto", \verb"break", \verb"continue", etc., tiene un coste temporal de ejecución constante, es decir,
\[
\alert{O(\mbox{instrucción simple}) = O(1)}.
\]
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una secuencia de instrucciones}
Una secuencia de $n$ instrucciones tiene un coste que es la suma de los costes de cada instrucción, es decir:
\[
\alert{O(\mbox{secuencia instrucciones}) = \sum_{i=1}^{n} O(\mbox{instrucción }i)}.
\]
El coste de una llamada a una función o un método es el coste de la secuencia de instrucciones de dicha función.
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una instrucción condicional}
\begin{itemize}
\item El coste de un condicional simple (típica sentencia \verb"if"), depende del coste de cada una de sus dos ramas. Si
\begin{itemize}
\item la rama \verb"if" tiene un coste $O(f_{\mbox{if}})$ y $\Omega(g_{\mbox{if}})$, y
\item la rama \verb"else" tiene un coste $O(f_{\mbox{else}})$ y $\Omega(g_{\mbox{else}})$,
\end{itemize}
entonces el coste del condicional es el coste de la rama cuya cota sea de mayor orden
\begin{align*}
\alert{O(\mbox{condicional simple})} & \alert{= O(\max (f_{\mbox{if}},f_{\mbox{else}}))}\\
\alert{\Omega(\mbox{condicional simple})} & \alert{= \Omega(\min (g_{\mbox{if}},g_{\mbox{else}}))}.
\end{align*}
\item En el caso de que un condicional tenga más de dos ramas (típica sentencia \verb"switch"), si decimos que cada rama $i$ tiene un coste $O(f_i)$ y $\Omega(g_i)$, podemos generalizar la anterior fórmula a:
\begin{align*}
\alert{O(\mbox{condicional})} & \alert{= O(\max_{i=1,\ldots n} (f_i))}\\
\alert{\Omega(\mbox{condicional})} & \alert{= \Omega(\min_{i=1,\ldots n} (g_i))}.
\end{align*}
\end{itemize}
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de un bucle}
Un bucle cualquiera se compone, en su forma más genérica, de los siguientes componentes:
\begin{itemize}
\item Inicialización del bucle: es un conjunto de instrucciones simples luego es $O(1)$.
\item Comprobación de la condición del bucle: de nuevo es una instrucción simple pero si se repite $k$ veces, es $O(k)$.
\item Incremento del contador del bucle: si existe es también una instrucción simple pero si se repite $k$ veces, también es $O(k)$.
\item Cuerpo del bucle: si consideramos que las sentencias que componen el cuerpo del bucle tiene un coste de $O(f)$, y que el bucle se ejecuta $k$ veces, entonces el coste de ejecución del bucle es de $O(kf)$.
\item Finalización del bucle: de nuevo si existe es $O(1)$.
\end{itemize}
Luego un bucle nos cuesta:
\begin{align*}
\alert{O(\mbox{bucle})} & \alert{= O(1) +O(n_{\max}) [+O(n_{\max})] + O(n_{\max}f) [+O(1)] = O(n_{\max}f)}\\
\alert{\Omega(\mbox{bucle})} & \alert{= \Omega(1) + \Omega(n_{\min}) [+\Omega(n_{\min})] + \Omega(n_{\min}f) [+\Omega(1)] = \Omega(n_{\min}f)}
\end{align*}
donde $n_{\max}$ y $n_{\min}$ es el número de vueltas del bucle en el peor y mejor caso respectivamente.
\end{frame}

%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo del coste temporal}
\framesubtitle{Sumatorio de una serie aritmética}
\begin{lstlisting}[mathescape]
// sumaAritmetica.java
public static double sumaAritmetica(double a1, double d, int n){
  double s, an;
  an = a1;                   #\alert{$\leftarrow$ $1$ paso}#
  s = a1;                    #\alert{$\leftarrow$ $1$ paso}#
  for (int i=2; i<=n; i++){  #\alert{$\leftarrow$ $2n$ pasos}#
    an += d;                 #\alert{$\leftarrow$ $2$ pasos ($n-1$ veces)}#
    s += an;                 #\alert{$\leftarrow$ $2$ pasos ($n-1$ veces)}#
  }
  return s;
}
\end{lstlisting}
El número de pasos es $t(n) = 3+2n+4(n-1) = 6n-1\in \Theta(n)$.
\end{frame}


\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Sumatorio de una serie aritmética}
Otra forma más sencilla de calcular el coste es
\begin{lstlisting}[mathescape]
// SumaAritmetica.java
public static double sumaAritmetica(double a1, double d, int n){
  double s, an;
  an = a1;                   #\alert{$\leftarrow$ $\Theta(1)$}#
  s = a1;                    #\alert{$\leftarrow$ $\Theta(1)$}#
  for (int i=2; i<=n; i++){  #\alert{$\leftarrow$ $n-1$ vueltas $\Theta(n)$}#
    an += d;                 #\alert{$\leftarrow$ $\Theta(1)$}#
    s += an;                 #\alert{$\leftarrow$ $\Theta(1)$}#
  }
  return s;
}
\end{lstlisting}
Se trata de un coste lineal $\Theta(n)$.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo del coste temporal}
\framesubtitle{Búsqueda de un elemento en un vector}
\begin{itemize}
\item Mejor caso (el elemento buscado ocupa la primera posición del vector):
\begin{lstlisting}[mathescape]
// Busqueda.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++)  #\alert{$\leftarrow$ $2$ pasos}#
    if (a[i]==x) return i;            #\alert{$\leftarrow$ $1$ pasos}#
  return -1;
}
\end{lstlisting}
El número de pasos es $t(n) = 3\in \Omega(1)$.

\item Peor caso (el elemento buscado no está en el vector):
\begin{lstlisting}[mathescape]
// Busqueda.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++)  #\alert{$\leftarrow$ $2n+2$ pasos}#
    if (a[i]==x) return i;            #\alert{$\leftarrow$ $1$ paso ($n$ veces)}#
  return -1;
}
\end{lstlisting}
El número de pasos es $t(n) = 3n+2\in O(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Búsqueda de un elemento en un vector}
\begin{itemize}
\item Mejor caso (el elemento buscado ocupa la primera posición del vector):
\begin{lstlisting}[mathescape]
// Busqueda.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++)  #\alert{$\leftarrow$ $\Omega(1)$}#
    if (a[i]==x) return i;            #\alert{$\leftarrow$ $\Omega(1)$}#
  return -1;
}
\end{lstlisting}
El omega es constante $\Omega(1)$.

\item Peor caso (el elemento buscado no está en el vector):
\begin{lstlisting}[mathescape]
// Busqueda.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++)  #\alert{$\leftarrow$ $O(n)$}#
    if (a[i]==x) return i;            #\alert{$\leftarrow$ $O(1)$}#
  return -1;
}
\end{lstlisting}
El orden es lineal $O(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo del coste temporal}
\framesubtitle{Búsqueda de un elemento en un vector ordenado}
\begin{itemize}
\item Mejor caso (el elemento buscado ocupa la primera posición del vector):
\begin{lstlisting}[mathescape]
// BusquedaOrdenada.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++){  #\alert{$\leftarrow$ $2$ pasos}#
    if (a[i]==x) return i;             #\alert{$\leftarrow$ $1$ pasos}#
    else if (a[i]>x) return -1;
  }
  return -1;
}
\end{lstlisting}
El número de pasos es $t(n)=2\in \Omega(1)$.

\item Peor caso (el elemento buscado no está en el vector y es mayor que cualquiera de los elementos del vector):
\begin{lstlisting}[mathescape]
// BusquedaOrdenada.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++){  #\alert{$\leftarrow$ $2n+2$ pasos}#
    if (a[i]==x) return i;             #\alert{$\leftarrow$ $1$ paso ($n$ veces)}#
    else if (a[i]>x) return -1;        #\alert{$\leftarrow$ $1$ paso ($n$ veces)}#
  }
  return -1;
}
\end{lstlisting}
El número de pasos es $t(n) = 4n+2\in O(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Búsqueda de un elemento en un vector ordenado}
\begin{itemize}
\item Mejor caso (el elemento buscado ocupa la primera posición del vector):
\begin{lstlisting}[mathescape]
// BusquedaOrdenada.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++){  #\alert{$\leftarrow$ $\Omega(1)$}#
    if (a[i]==x) return i;             #\alert{$\leftarrow$ $\Omega(1)$}#
    else if (a[i]>x) return -1;}
  return -1;
}
\end{lstlisting}
El omega es constante $\Omega(1)$.

\item Peor caso (el elemento es mayor que los elementos del vector):
\begin{lstlisting}[mathescape]
// BusquedaOrdenada.java
public static int busqueda(int[] a, int x){
  for (int i = 0; i < a.length; i++){  #\alert{$\leftarrow$ $O(n)$}#
    if (a[i]==x) return i;             #\alert{$\leftarrow$ $O(1)$}#
    else if (a[i]>x) return -1; }      #\alert{$\leftarrow$ $O(1)$}#
  return -1;
}
\end{lstlisting}
El orden es lineal $O(n)$.
\begin{center}
\emph{\alert{¡Aunque mejora el coste promedio, en el peor caso no hemos ganado nada!}}
\end{center}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Búsqueda dicotómica}
Estudiemos ahora el algoritmo de búsqueda dicotómica en un vector ordenado:
\begin{lstlisting}[mathescape]
// BusquedaDicotomica.java
public static int busquedaDicotomica(int[] a, int x){
  int i, desde=0, hasta=a.length-1;
  while (desde<hasta){
    i=(desde+hasta)/2;
    if (a[i]==x) return i;
    else if (a[i]>x) hasta=i-1;
    else desde=i+1;
  }
  return -1;
}
\end{lstlisting}
\begin{center}
\emph{¿Mejorará el coste con respecto al algoritmo de búsqueda anterior?}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Búsqueda dicotómica}
El mejor caso ocurre cuando el elemento buscado ocupa la posición central del vector. En tal caso el coste es:
\begin{lstlisting}[mathescape]
// BusquedaDicotomica.java
public static int busquedaDicotomica(int[] a, int x){
  int i, desde=0, hasta=a.length-1;    #\alert{$\leftarrow$ $\Omega(1)$}#
  while (desde<hasta){                 #\alert{$\leftarrow$ $\Omega(1)$}#
    i=(desde+hasta)/2;                 #\alert{$\leftarrow$ $\Omega(1)$}#
    if (a[i]==x) return i;             #\alert{$\leftarrow$ $\Omega(1)$}#
    else if (a[i]>x) hasta=i-1;
    else desde=i+1;
  }
  return -1;
}
\end{lstlisting}
es decir, constante $\Omega(1)$.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Búsqueda dicotómica}
\begin{itemize}
\item El peor caso ocurre de nuevo cuando el elemento buscado no está en el vector.
\item En tal caso,
\begin{center}
\emph{¿cuántas vueltas dará el bucle?}
\end{center}

\item La clave está en entender que con cada iteración del bucle el tamaño del problema (el número de elementos entre \texttt{desde} y \texttt{hasta}) se reduce a la mitad:
\begin{itemize}
\item Primera iteración: $n/2$,
\item Segunda iteración: $n/4$,
\item ...
\item $k$-ésima iteración: $n/2^k$.
\end{itemize}
\item En la última iteración el tamaño del problema es $1$, es decir $n/2^k=1$. Tomando logaritmos y despejando podemos ver el número de vueltas que da el bucle:
\[
\log_2 \frac{n}{2^k}=\log_2 1 = 0 \Leftrightarrow \log_2 n -\log_2 2^k =0 \Leftrightarrow \log_2 n -k = 0 \Leftrightarrow k =\log_2 n
\]
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste temporal}
\framesubtitle{Búsqueda dicotómica}
Así pues, en el peor caso el coste es:
\begin{lstlisting}[mathescape]
// BusquedaDicotomica.java
public static int busquedaDicotomica(int[] a, int x){
  int i, desde=0, hasta=a.length-1;    #\alert{$\leftarrow$ $O(1)$}#
  while (desde<hasta){                 #\alert{$\leftarrow$ $O(\log n)$}#
    i=(desde+hasta)/2;                 #\alert{$\leftarrow$ $O(1)$}#
    if (a[i]==x) return i;             #\alert{$\leftarrow$ $O(1)$}#
    else if (a[i]>x) hasta=i-1;        #\alert{$\leftarrow$ $O(1)$}#
    else desde=i+1;                    #\alert{$\leftarrow$ $O(1)$}#
  }
  return -1;
}
\end{lstlisting}
es decir, logarítmico $O(\log n)$.
\begin{center}
  \emph{\alert{¡Mejora al algoritmo de búsqueda lineal!}}
\end{center}
\end{frame}


\subsection{Coste temporal en algoritmos recursivos}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Cálculo del coste temporal en algoritmos recursivos}
\begin{itemize}
\item Los algoritmos recursivos son un poco más difíciles de analizar.
\item El principal problema consiste en determinar o acotar el número de llamadas recursivas.
\item Generalmente lo haremos mediante una ecuación de recurrencia como la utilizada en el cálculo del coste del algoritmo de búsqueda dicotómica.
\item Veamos algunos ejemplos:
\begin{itemize}
\item Cálculo del factorial de un número.
\item Cálculo de una exponenciación ($a^n$).
\item Cálculo de números de Fibonacci.
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Determinación del nº de llamadas de una función recursiva}
\framesubtitle{Algoritmo para calcular el factorial de un número}
\begin{itemize}
\item El siguiente algoritmo calcula el factorial de un número de manera recursiva:
\begin{lstlisting}[mathescape]
// Factorial.java
public static int factorial(int n){
  if (n==0) return 1;
  else return n * factorial(n-1);
}
\end{lstlisting}
\item Para calcular su coste, podemos expresar el número de llamadas recursivas mediante una ecuación de recurrencia:
\[
t(n)=
\left\{
  \begin{array}{ll}
    1, & \hbox{si $n=0$;} \\
    1+t(n-1), & \hbox{si $n>0$.}
  \end{array}
\right.
\]

\item La ecuación es similar al programa en tanto que presenta recursión en los mismos puntos en los que el programa efectúa llamadas recursivas.

\begin{center}
\emph{\alert{¡Para calcular el coste tendremos que resolver la ecuación!}}
\end{center}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Resolución de recurrencias}
\framesubtitle{Técnica de desplegado}
\begin{itemize}
\item Hay una técnica, conocida por \textbf{desplegado}, que permite obtener una expresión no recursiva para $t(n)$.
\item Consiste en ir expandiendo la expresión recursiva sustituyendo cualquier término de la forma $t(i)$ por su parte derecha, es decir:
\begin{align*}
t(n) &= 1+t(n-1) = 1+1+t(n-2) = \stackrel{n\textrm{ veces}}{\cdots} = 1+\stackrel{n\textrm{ veces}}{\cdots}+1+t(0) = \\
&= 1+ \stackrel{n+1\textrm{ veces}}{\cdots}+1 = n+1.
\end{align*}

\item Así pues, el número de llamadas recursivas es n+1.

\item Como las operaciones que se realizan dentro del cuerpo de cada llamada (a excepción de las propia llamada recursiva) tienen un coste $\Theta(1)$, concluimos que el coste del algoritmo es $\Theta(n)\Theta(1)=\Theta(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Resolución de recurrencias}
\framesubtitle{Inducción constructiva}
\begin{itemize}
\item La técnica del desplegado no constituye, por sí misma, una demostración formal de que $t(n)=n+1$, pues hemos efectuado un ``salto'' en la serie de igualdades sin más justificación que la que proporciona la intuición.

\item Lo que hace la técnica es proporcionar una expresión para el coste que podemos demostrar ahora por inducción.

\item Veamos por la función de recurrencia
\[
t(n)=
\left\{
  \begin{array}{ll}
    2, & \hbox{si $n=0$;} \\
    n^2+2t(n-1), & \hbox{si $n>0$.}
  \end{array}
\right.
\]
tiene orden $O(2^n)$ por inducción:
\begin{itemize}
\item Caso base: Para $n=0$, $t(0)=2\in O(1)=O(2^0)$.
\item Caso general: Supongamos que $t(n-1)\in O(2^{n-1})$, entonces $t(n-1)\leq c2^{n-1}$ para $n>n_0$. De aquí se deduce
\[
t(n)=n^2+2t(n-1)\leq n^2+2c2^{n-1}= n^2+c2^n \in O(2^n).
\]
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Determinación del nº de llamadas de una función recursiva}
\framesubtitle{Algoritmo para calcular potencias}
\begin{itemize}
\item El siguiente algoritmo calcula recursivamente $a^n$:
\begin{lstlisting}[mathescape]
// Potencia.java
public static double potencia(double a, int n){
  if (n==0) return 1;
  else return a * potencia(a, n-1);
}
\end{lstlisting}

\item La ecuación de recurrencia asociada es:
\[
t(n)=
\left\{
  \begin{array}{ll}
    1, & \hbox{si $n=0$;} \\
    1+t(n-1), & \hbox{si $n>0$.}
  \end{array}
\right.
\]
y como en el caso del factorial, el coste es $\Theta(n)$.

\begin{center}
\emph{\alert{¿Se puede construir un algoritmo más eficiente?}}
\end{center}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Determinación del nº de llamadas de una función recursiva}
\framesubtitle{Algoritmo eficiente para calcular potencias}
\begin{itemize}
\item Hay una poderosa idea que nos permite construir un algoritmo más eficiente:
\begin{lstlisting}[mathescape]
// Potencia2.java
public static double potencia2(double a, int n){
  double r;
  if (n==0) return 1;
  if (n==1) return a;
  r = potencia(a, n/2);
  if (n % 2 == 0) return r * r;
  else return a * r * r;
}
\end{lstlisting}

\item Este algoritmo se basa en la siguiente propiedad:
\begin{itemize}
  \item Si $n$ es par, entonces $a^n=a^{n/2}a^{n/2}$.
\item Si $n$ es impar, entonces $a^n=a^{(n-1)/2}a^{(n-1)/2}a$.
\end{itemize}
\item La ventaja de este algoritmo es que en cada llamada recursiva, en lugar de reducir el tamaño a $n-1$, lo reduce a la mitad.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Determinación del nº de llamadas de una función recursiva}
\framesubtitle{Algoritmo eficiente para calcular potencias}
\begin{itemize}
\item La ecuación de recurrencia asociada al algoritmo anterior es:
\[
t(n)=
\left\{
  \begin{array}{ll}
    1, & \hbox{si $n\leq 1$;} \\
    1+t(n/2), & \hbox{si $n>1$.}
  \end{array}
\right.
\]
\item Aplicando la técnica de desplegado, y suponiendo, sin pérdida de generalidad, que $n$ es par, tenemos :
\begin{align*}
t(n) &= 1+t(n/2) = 1+1+t(n/4) = \stackrel{\log_2n\textrm{ veces}}{\cdots} = 1+\stackrel{\log_2n\textrm{ veces}}{\cdots}+1+t(1) = \\
&= 1+ \stackrel{\log_2n+1\textrm{ veces}}{\cdots}+1 = \log_2n+1.
\end{align*}

\item Así pues, el número de llamadas recursivas es $\Theta(\log n)$ y como las operaciones que se realizan dentro del cuerpo de cada llamada (a excepción de las propia llamada recursiva) tienen un coste $\Theta(1)$, concluimos que el coste del algoritmo es $\Theta(\log n)\Theta(1)=\Theta(\log n)$, que \emph{¡es mas eficiente que el anterior!}
\begin{center}
\emph{¿Se podría mejorar aún más reduciendo el tamaño del problema a $n/3$ en cada llamas?}
\end{center}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Determinación del nº de llamadas de una función recursiva}
\framesubtitle{Algoritmo para calcular la serie de Fibonacci}
\begin{itemize}
\item El siguiente algoritmo calcula el término $n$ de la serie de Fibonacci.
\begin{lstlisting}[mathescape]
// Fibonacci.java
public static long fibonacci(int n){
  if (n<=2) return 1;
  else return fibonacci(n-2)+fibonacci(n-1);
}
\end{lstlisting}

\item La ecuación de recurrencia asociada es:
\[
t(n)=
\left\{
  \begin{array}{ll}
    1, & \hbox{si $n\leq 2$;} \\
    1+t(n-1)+t(n-2), & \hbox{si $n>2$.}
  \end{array}
\right.
\]
\item En este caso, para simplificar el desplegado, vamos a acotar el número de llamadas:
\begin{align*}
t(n) &= 1+t(n-1)+t(n-2) \leq 1+2t(n-1) = 1+2(1+2t(n-2))=\\
&= 1+2+4t(n-2) =\stackrel{n\textrm{ veces}}{\cdots} = \sum_{i=0}^n 2^i = 2^{n+1}-2.
\end{align*}
y en consecuencia, el coste es $\Theta(2^n)$.
\begin{center}
  \emph{¿Podrías construir una versión iterativa más eficiente?}
\end{center}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Recurrencias por resta}
En una recurrencia por resta el tamaño del problema disminuye en una constante $b$ en cada llamada recursiva o iteración.
\[
t(n)=
\left\{
  \begin{array}{ll}
    cn^k, & \hbox{si $n\leq b$;} \\
    at(n-b)+cn^k, & \hbox{si $n>b$.}
  \end{array}
\right.
\]
En tal caso el coste es
\[
t(n)\in
\left\{%
\begin{array}{ll}
    \Theta(n^k), & \hbox{si $a<1$;} \\
\Theta(n^{k+1}), & \hbox{si $a=1$;} \\
\Theta(a^{n\div b}), & \hbox{si $a>1$.} \\
\end{array}%
\right.
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Recurrencias por cociente}
En una recurrencia por cociente el tamaño del problema disminuye dividiendo por una constante $b$ en cada llamada recursiva o iteración.
\[
t(n)=
\left\{
  \begin{array}{ll}
    cn^k, & \hbox{si $n\leq b$;} \\
    at(n/b)+cn^k, & \hbox{si $n>b$.}
  \end{array}
\right.
\]
En tal caso el coste es
\[
t(n)\in
\left\{%
\begin{array}{ll}
    \Theta(n^k), & \hbox{si $a<b^k$;} \\
\Theta(n^k\log n), & \hbox{si $a=b^k$;} \\
\Theta(n^{\log_b a}), & \hbox{si $a>b^k$.} \\
\end{array}%
\right.
\]
\end{frame}


\subsection{Coste temporal del manejo de estructuras de datos}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Costes asociados a estructuras de datos}
Vamos a analizar la complejidad de las operaciones básicas que se realizan sobre las estructuras de datos más comunes:
\begin{itemize}
\item Lista no ordenada.
\item Lista ordenada.
\item Vector no ordenado.
\item Vector ordenado.
\item Árbol binario.
\item Árbol binario de búsqueda.
\item Árbol binario de búsqueda completo y balanceado.
\end{itemize}
Denotaremos mediante $n$ al tamaño de todas las estructuras de datos.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de un recorrido (traversal)}
\begin{itemize}
\item Un \textbf{recorrido} consiste en visitar \emph{al menos una vez} todos los elementos de una colección.

\item Como en un recorrido hay que visitar todos los elementos, su coste es necesariamente $\Omega(n)$ para cualquier estructura de datos. Generalmente también es $\Theta(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una búsqueda}
\begin{itemize}
\item Una \textbf{búsqueda} consiste en determinar si un elemento es miembro o no de la colección.

\item Hay dos tipos de búsqueda:
\begin{itemize}
\item \textbf{Búsqueda lineal o simple}. Si la colección no está ordenada hay que realizar una búsqueda lineal.
Vimos en un ejemplo anterior que en el peor de los casos es necesario visitar todos los elementos, con lo que el coste es $O(n)$.
\item \textbf{Búsqueda binaria o dicotómica}. Si la colección está ordenada y dispone de acceso aleatorio a los elementos, entonces podemos utilizar una búsqueda binaria.
Vimos en un ejemplo anterior que el coste era $O(\log n)$.
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una inserción}
\begin{itemize}
\item Insertar un elemento en una colección es una operación que se compone de dos pasos:
\begin{itemize}
\item Encontrar el lugar apropiado para la inserción, y
\item Realizar la inserción del elemento.
\end{itemize}

\item El coste de la inserción será la suma de los costes de los dos pasos.

\item Su cálculo es diferente dependiendo de si la estructura está ordenada o no:
\begin{itemize}
\item \textbf{Estructuras no ordenadas}. Si la estructura de datos no está ordenada, cualquier posición sirve para la inserción. El coste será constante $O(1)$.
\item \textbf{Estructuras ordenadas}. Si la estructura de datos está ordenada, hay que hilar algo más fino. En las siguientes diapositivas vemos los distintos casos.
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una inserción en una lista ordenada}
\begin{itemize}
\item La búsqueda del lugar apropiado es $O(n)$ ya que al no tener acceso aleatorio a los elementos de la lista, no podemos aplicar una búsqueda binaria.
\item Una vez encontrado el lugar, realizar la inserción es cosa de $4$ ó $5$ instrucciones, así que supone un coste $O(1)$.
\item Así pues, el coste total es $O(n)+O(1)=O(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una inserción en un vector ordenado}
\begin{itemize}
\item Ahora si podemos emplear una búsqueda binaria para localizar el lugar de inserción adecuado, por lo que la localización es $O(\log n)$.
\item Pero para hacer sitio en el vector al nuevo elemento, hemos de desplazar a la derecha todos los elementos del vector mayores que él. \emph{¿Cuál es el coste de esta operación?}
\item Poniéndonos en el peor caso (el elemento ha de ser insertado al principio del vector) hemos de desplazar $n$ elementos, es decir, estamos hablando de $O(n)$ ya que el coste de desplazar un solo elemento es constante.
\item Por tanto, el coste total es $O(\log n)+O(n)= O(n)$.

Es decir, \emph{¡igual que en el caso anterior!}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una inserción en un árbol de búsqueda no balanceado}
\begin{itemize}
\item El árbol no está completo ni balanceado, por lo que la búsqueda, como ya hemos visto, ha de ser lineal, y su coste es $O(n)$ (¡Recuerda que un caso degenerado de árbol binario no balanceado es una lista!)
\item La inserción consiste simplemente en colgar el nuevo nodo en el árbol, que es $O(1)$.

\item Por tanto, el coste total es $O(n)+O(1)= O(n)$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste de una inserción en un árbol de búsqueda completo y balanceado}
\begin{itemize}
\item En este caso el coste de encontrar el lugar correcto es $O(\log n)$, ya que podemos realizar una búsqueda binaria.

\item De nuevo la inserción consiste en colgar el nuevo nodo en el árbol, que es $O(1)$.

\item El coste total es $O(\log n) + O(1)= O(\log n)$.

\begin{center}
\emph{Pero, ¡falta sumar el coste de mantener el árbol balanceado!}
\end{center}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Resumen de costes asociados a estructuras de datos}
\begin{center}
\rowcolors{1}{blue!10!white}{blue!20!white}
\arrayrulewidth 0.8pt
\begin{tabular}{|l|c|c|c|}
\hline \rowcolor{white!90!black}
 Estructuras de datos                    & Recorrido &  Búsqueda   &  Inserción  \\
\hline\hline
 Lista no ordenada                       &  $O(n)$   &   $O(n)$    &   $O(1)$    \\
\hline
 Lista ordenada                          &  $O(n)$   &   $O(n)$    &   $O(n)$    \\
\hline
 Vector no ordenado                      &  $O(n)$   &   $O(n)$    &   $O(1)$    \\
\hline
 Vector ordenado                         &  $O(n)$   & $O(\log n)$ &   $O(n)$    \\
\hline
 Árbol binario                           &  $O(n)$   &   $O(n)$    &   $O(1)$    \\
\hline
 Árbol binario de búsqueda no balanceado &  $O(n)$   &   $O(n)$    &   $O(n)$    \\
\hline
 Árbol binario de búsqueda balanceado    &  $O(n)$   & $O(\log n)$ & $O(\log n)$ \\
\hline
\end{tabular}
\end{center}
\end{frame}


\subsection{Análisis de la complejidad espacial}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste espacial}
\begin{itemize}
\item La \textbf{complejidad espacial} es el estudio de la eficiencia de los algoritmos en lo relativo a su consumo de memoria.

\item Un razonamiento similar al seguido con el coste temporal nos lleva a considerar únicamente la evolución del consumo de memoria con el tamaño del problema.

\item En el estudio asintótico no nos preocupa que un programa use la mitad o el doble de memoria que otro, pero sí que use una cantidad de memoria que crece con el cuadrado de $n$ cuando otro requiere sólo una cantidad de memoria constante.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste computacional espacial}
\begin{itemize}
\item El concepto de paso utilizado en los análisis de coste temporal tiene su análogo en el estudio del coste espacial en el concepto de \textbf{celda de memoria}.

\item No importa si una variable ocupa 2, 4 u 8 bytes. Sólo importa si su tamaño es o no es función (y de qué orden) del tamaño del problema.

\begin{definicion}[Coste computacional espacial]
Se llama \textbf{coste computacional espacial} de un programa al número de celdas de memoria del programa expresado en función del tamaño del problema.
\end{definicion}

\item Al igual que para el coste temporal, el coste espacial suele catalogarse dentro de una familia de cotas superiores e inferiores para el consumo de memoria.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Cálculo del coste espacial en algoritmos no recursivos}
El estudio de la complejidad espacial de los \textbf{algoritmos no recursivos} es relativamente sencillo:
\begin{itemize}
\item Las variables y constantes de tipos predefinidos (enteros, reales, lógicos, etc.) tiene un coste $\Theta(1)$.
\item Un array de $k$ elementos de un tipo con coste $\Theta(f)$ tiene un coste $\Theta(kf)$.
\item Un registro o estructura con $k$ campos con costes asociados $\Theta(f_1),\ldots,\Theta(f_k)$ tiene un coste $\Theta(f_1)+\cdots+\Theta(f_k)$.
\end{itemize}
\begin{center}
\emph{\alert{¡Cuidado con la generación de memoria dinámica!}}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Cálculo del coste espacial en algoritmos recursivos}
\begin{itemize}
\item Como ocurre en el estudio de la complejidad temporal, el coste espacial de los \textbf{algoritmos no recursivos} depende del número de llamadas que se realice (tanto en el mejor como en el peor caso).

\item Aunque una rutina recursiva sólo utilice variables escalares, puede requerir espacio $\Theta(n)$ si efectúa del orden de $n$ llamadas recursivas para solucionar un problema de tamaño $n$.

\item En cada llamad recursiva hay que contabilizar el espacio de memoria que se reserva en la pila de la recursividad.

\item También hay que tener en cuenta si el paso de parámetros se realiza por valor o por referencia, ya que este último no supone un gasto adicional de memoria en las llamadas recursivas.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Ejemplo de cálculo asintótico del coste espacial}
\framesubtitle{Búsqueda dicotómica recursiva}
\begin{lstlisting}[mathescape]
// BusquedaDicotomicaRecursiva.java
public static int busquedaDicotomica(int[] a, int x, int desde, int hasta){
  if (desde<hasta) return -1;
  else {
    i=(desde+hasta)/2;
    if (a[i]==x) return i;
    else if (a[i]>x) return busquedaDicotomica(a,x,desde,i-1);
    else return busquedaDicotomica(a,x,i+1,hasta);
  }
}
\end{lstlisting}
\begin{center}
\emph{¿Cuál es su coste espacial?}
\end{center}
\end{frame}